The present invention is generally related to the field of signal processing and, more particularly, to the field of programmable hardware and/or software filtering systems and methods of image data in compact, efficient computing architectures.
In the arts it is often necessary to manipulate a received signal or image, for both practical and operational reasons. For instance, the signal may need to be enhanced prior to some secondary operation being performed on the data such as printing with a laser printer. A scanned image may eventually need to be restored or reconstructed to its original form. Other operations can take the form of resolution conversion, thinning or thickening, among others. In order to manipulate the received signal or image data in these instances, mathematical operations are often performed. To achieve this, the discrete signal or image is often converted into or represented by a mathematical sequence or array of discrete values. For example, binary signals or images often take the form of discrete values of [0,1] and 8-bit gray-scale images often take the form of values in the range of [0 255]. The field of discrete signal and image processing, both theoretical and applied, is relatively dominated by mathematics in the form of specific methods and applications.
Many methods of signal or image processing use one or more applications involving filters. A filter operates by capturing a windowed observation of an image or signal. A windowed observation is a collection or vector of samples from the captured image or signal. Based on this vector, a decision, based on some formula or algorithm, is made about the image or signal at a particular position within the image or signal. In general, a filter operates on a set of signal or image samples which are mathematically written as a vector having the form of (X1, . . . , XN).
Many techniques can be found in the arts, of which the following are representative and which are hereby incorporated by reference being made thereto. For example, a filter can assign a new sample value to the center pixel of a window in order to accomplish the overall goal of a restoration or enhancement of a degraded image, as taught by Enhancement and Restoration of Digital Documents, R. P. Loce and E. R. Dougherty, SPIE Press, 1997, and Enhancement of Digital Documents, R. P. Loce and E. R. Dougherty, Electronic Imaging Technology, SPIE Press 1999, and Two-Dimensional Signal and Image Processing, J. S. Lim, Prentice Hall, 1990. Many other operations are found in the known literature. Furthermore, other applications of filters used in signal or image processing include, resolution conversion, object detection, speckle-removal, and edge enhancement.
Nonlinear image or signal processing is a general representation of signal or image filtering based on a logical decomposition of a filter into a set of relatively simple operators. Any windowed increasing shift-invariant filter can be represented as a combination of simple operations called erosions as taught by Nonlinear Filters for Image Processing, E. R. Dougherty and J. Astola (eds.), SPIE/IEEE Press, 1999. The term nonlinear refers to the entire class of windowed filters that includes linear filters, i.e., those filters computed by convolution.
Since filters can be highly complex and repeatedly be executed millions of times in rapid succession in order to perform a single operation on a given image or signal, what is needed in the arts are compact, efficient computing architectures directed towards this end. Efficient architectures depend on filter representations. If a filter can be broken down into its base operations, it might be possible to execute the relatively simple operations in parallel in order to achieve high-speed execution and overall efficiency.
Computational Gray-Scale Morphology on Lattices (A Comparator-Based Image Algebra) Part I: Architecture, E. R. Dougherty and D. Sinha, Real Time Imaging, Vol.1, No.1, 1995, teaches a computer architecture using representations that perform tests in parallel. The representational methods as taught therein express any filtering operation as a collection of logical tests or operations wherein each logical test is associated with a value. If a windowed observation satisfies a test, the filter output is then associated with that value. Although the above architecture is not practical for filters requiring many tests, it does teach general representational method.
Increasing filters are of special interest in the art of signal processing because they can be more efficiently implemented. An increasing filter F has the mathematical property that if (x1, . . . , xN) less than =(y1, . . . , yN), then F(x1, . . . , xN) less than =F(y1, . . . , yN). It is known in the art that increasing filters can have two orders of magnitude fewer logical comparisons in their representations that a general non-increasing filter. Applications of increasing filters known in the art are thinning, thickening, hole-filling, restoration of ragged edges, resolution conversion, median filtering, and noise removal.
It is the aim of the present invention to overcome the conventional prior art print limitations, as described above, by programming a computational architecture to perform logical comparisons in a more compact and efficient way.
An increasing nonlinear-filter represented as a plurality of basis elements along with the filter values at those basis elements by finding, for each output value k of the filter, all possible observations X that result in an output value k or greater. The set of all values that map to an output value k or greater have at least one minimal element at these are known in the art as basis elements. These basis elements are arranged in a list, numbered 1 through M. Constructing a table in which basis element number corresponds to the filter output value at that basis element. Thereafter, each of the N samples (X1, . . . , XN) is inspected in turn. For each sample Xi, testing each of its possible values with its respective interval components wherein, if the M basis elements are A1, . . . , AM and if basis element number 1 is being inspected, then each value of X1 is tested against Aij. For each value of Xi=t1, . . . , tG, put an entry xe2x80x981xe2x80x99 in table BV[j][k][m] if tk is greater than or equal to Aij and put an entry xe2x80x980xe2x80x99 in a table BV[j][k][m], otherwise. A table linking bit vector positions to filter output values is thereafter generated by computing filter values at each basis element. The list is sorting in increasing order. The position of the sorted output values corresponds to bit vector positions. For example, position 0 corresponds to the least filter value for a basis element and position Mxe2x88x921 corresponds to the greatest filter value for a basis element. In such a manner, the output values of filter of the present invention are readily obtainable by a small deterministic sequence of table lookups and a set of bit-wise logical operations.